/**
 * A星寻路算法类
 * 实现了基于网格的八方向寻路
 */
class AStar {
    constructor() {
        // 定义8个方向的偏移量：左上、上、右上、左、右、左下、下、右下
        this.dirs = [
            [-1, -1], [0, -1], [1, -1],  // 上方三个方向
            [-1, 0],           [1, 0],    // 左右两个方向
            [-1, 1],  [0, 1],  [1, 1]     // 下方三个方向
        ];
    }

    /**
     * 寻找从起点到终点的最短路径
     * @param {Object} start - 起点坐标 {x, y}
     * @param {Object} end - 终点坐标 {x, y}
     * @param {Array<Array<number>>} grid - 地图网格数据
     * @returns {Array|null} - 返回路径点数组或null（无路径）
     */
    findPath(start, end, grid) {
        const openList = [];          // 待检查的节点列表
        const closedList = new Set(); // 已检查的节点集合
        const cameFrom = new Map();   // 记录每个节点的来源节点
        
        const gScore = new Map();     // 从起点到当前节点的实际代价
        const fScore = new Map();     // 从起点经过当前节点到终点的估计总代价
        
        // 初始化起点
        const startKey = `${start.x},${start.y}`;
        gScore.set(startKey, 0);
        fScore.set(startKey, this.heuristic(start, end));
        
        openList.push({
            pos: start,
            f: fScore.get(startKey)
        });

        // 主循环
        while (openList.length > 0) {
            // 按f值排序，取出f值最小的节点
            openList.sort((a, b) => a.f - b.f);
            const current = openList.shift().pos;
            const currentKey = `${current.x},${current.y}`;

            // 到达终点，重建并返回路径
            if (current.x === end.x && current.y === end.y) {
                return this.reconstructPath(cameFrom, current);
            }

            closedList.add(currentKey);

            // 检查8个方向的相邻节点
            for (const [dx, dy] of this.dirs) {
                const neighbor = {
                    x: current.x + dx,
                    y: current.y + dy
                };

                const neighborKey = `${neighbor.x},${neighbor.y}`;

                // 检查边界
                if (neighbor.x < 0 || neighbor.x >= grid[0].length ||
                    neighbor.y < 0 || neighbor.y >= grid.length ||
                    closedList.has(neighborKey)) {
                    continue;
                }

                // 检查是否是障碍物（除了0以外都是障碍物）
                if (grid[neighbor.y][neighbor.x] !== 0) {
                    continue;
                }

                // 检查斜向移动时的相邻格子
                if (dx !== 0 && dy !== 0) {
                    // 检查水平相邻格子
                    if (grid[current.y][current.x + dx] !== 0) {
                        continue;
                    }
                    // 检查垂直相邻格子
                    if (grid[current.y + dy][current.x] !== 0) {
                        continue;
                    }
                }

                // 计算从起点经过当前节点到相邻节点的代价
                // 斜向移动代价为√2，直线移动代价为1
                const tentativeGScore = gScore.get(currentKey) + 
                    (dx === 0 || dy === 0 ? 1 : Math.SQRT2);

                // 如果找到更好的路径，更新节点信息
                if (!gScore.has(neighborKey) || tentativeGScore < gScore.get(neighborKey)) {
                    cameFrom.set(neighborKey, current);
                    gScore.set(neighborKey, tentativeGScore);
                    fScore.set(neighborKey, tentativeGScore + this.heuristic(neighbor, end));

                    // 检查节点是否已在开放列表中
                    const existingIndex = openList.findIndex(item => 
                        item.pos.x === neighbor.x && item.pos.y === neighbor.y);

                    if (existingIndex === -1) {
                        openList.push({
                            pos: neighbor,
                            f: fScore.get(neighborKey)
                        });
                    }
                }
            }
        }

        return null; // 没有找到可行路径
    }

    /**
     * 启发函数：计算两点间的曼哈顿距离
     * @param {Object} a - 起点坐标
     * @param {Object} b - 终点坐标
     * @returns {number} - 估计距离
     */
    heuristic(a, b) {
        return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
    }

    /**
     * 重建从起点到终点的路径
     * @param {Map} cameFrom - 节点来源记录
     * @param {Object} current - 当前节点
     * @returns {Array} - 路径点数组
     */
    reconstructPath(cameFrom, current) {
        const path = [current];
        let currentKey = `${current.x},${current.y}`;

        while (cameFrom.has(currentKey)) {
            current = cameFrom.get(currentKey);
            currentKey = `${current.x},${current.y}`;
            path.unshift(current);
        }

        return path;
    }
} 